翻訳と辞書
Words near each other
・ Computer Aided Verification
・ Computer algebra system
・ Computer America
・ Computer analyst
・ Computer and Internet Protocol Address Verifier
・ Computer and Management Institute
・ Computer and network surveillance
・ Computer and Video Games
・ Computer animation
・ Computer Animation and Social Agents
・ Computaris
・ Computation
・ Computation and Neural Systems
・ Computation history
・ Computation in the limit
Computation of cyclic redundancy checks
・ Computation of radiowave attenuation in the atmosphere
・ Computation offloading
・ Computation tree
・ Computation tree logic
・ Computational aeroacoustics
・ Computational algebra
・ Computational and Mathematical Organization Theory
・ Computational and Statistical Genetics
・ Computational and Structural Biotechnology Journal
・ Computational and Systems Neuroscience
・ Computational and Theoretical Chemistry
・ Computational archaeology
・ Computational astrophysics
・ Computational auditory scene analysis


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Computation of cyclic redundancy checks : ウィキペディア英語版
Computation of cyclic redundancy checks

Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that exclusive OR operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register, and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated) through byte-wise parallelism and space-time tradeoffs.
Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final exclusive OR step and, most critically, a bit ordering (endianness). As a result, the code seen in practice deviates confusingly from "pure" division,〔 and the register may shift left or right.
== Example ==

As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character "W", which is binary 010101112, decimal 8710, or hexadecimal 5716. For illustration, we will use the CRC-8-ATM (HEC) polynomial x^8+x^2+x+1. Writing the first bit transmitted (the coefficient of the highest power of x) on the left, this corresponds to the 9-bit string "100000111".
The byte value 5716 can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial M(x). Msbit-first, this is x^6+x^4+x^2+x+1 = 01010111, while lsbit-first, it is x^7+x^6+x^5+x^3+x = 11101010. These can then be multiplied by x^8 to produce two 16-bit message polynomials x^8 M(x).
Computing the remainder then consists of subtracting multiples of the generator polynomial G(x). This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions borrow "from infinity" instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.
|}
Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero; at the end, a group which is unchanged from the original; and a blue shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group becomes one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left.
In the msbit-first example, the remainder polynomial is x^7+x^5+x. Converting to a hexadecimal number using the convention that the highest power of ''x'' is the msbit; this is A216. In the lsbit-first, the remainder is x^7+x^4+x^3. Converting to hexadecimal using the convention that the highest power of ''x'' is the lsbit, this is 1916.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Computation of cyclic redundancy checks」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.